Recent years have seen the rapid advancement and proliferation of electronic devices, which devices often require the updating of the resident firmware, operating code, applications or other software loaded thereon, collectively, “binary images”, or simply “images”. Moreover, installing and updating of such binary images is becoming more routine where advancements applicable to a particular device far outpace the rate at which it is desirable to retire the unit and replace it with an entirely new unit.
Moreover, for many devices for which updating the binary image is desirable, these same devices may be remotely located and it is not practical for many reasons to return or collect the device in order that it can be directly connected to a host updating machine or system.
Additionally, with limited memory on the device itself, whether it be a mobile phone, PDA, pager or any other variety of small form factor portable device, delivery of an entire new image is often infeasible due to the capacity limitations of the device. Also, even if the device is not memory or other resource constrained, and thus not limiting the size or application process for installing an update, delivery of a complete new image may still be infeasible because the connection used by the device may be intermittent and/or of a limited capacity.
Also, in applying an update to install a new image, it is not uncommon for power loss or other interruptions to the subject device to occur which leads to failure of the installation. This may result in the installation process having to begin again from the start, or worse, leaving a device disabled or wholly inoperable due to a partial install from which it cannot recover or reinitiate.
Accordingly there is a need for an efficient, effective and reliable system and method for providing an update to a device that does not require the unit to be returned to a service center for update and instead uses an update package that can modify the binary image in-situ, and is significantly smaller than the full image. And, there exists need for a complimentary mechanism or technique to allow for recovery and continued application of an update to such device, even when being updated remotely and without access to a host update or boot rescue system.
A known manner in reducing the size of a new image update is to use a differencing algorithm or binary differencing engine (BDE) which compares the current or existing binary image with the new binary image to produce a list of differences. Such differences, in a general sense, are typically output or expressed as sequences or sets of ADD and COPY operations such that the new image can be created by cobbling together binary strings copied from image sequences resident on the device in the original image and interlacing them with binary sequences from the new image for which a suitable copy string was not available in the old image. The ADD operation specifies a list of bytes that must be copied into the new image at the current location, and the COPY operation specifies a number of bytes to be copied from a given location in the original image to the current update location in the new image.
The efficiency of the high-level BDE can have significant effect on how much of the update can be expressed as COPY operations and how much using ADD operations; in general terms, the more of the new image that can be expressed as COPY operations the smaller the resultant update package will be. Quite naturally, at one extreme, a single add operation comprising the entire new image is too large and does nothing to reduce the size of the update package. Similarly, any new image can be made entirely from copy operations if the copy sequences are short enough, say, ultimately, copying sequences of single bits; however, at that extreme the required number of total operations is prohibitively high and, again, does not benefit the reducing the size of the update package. Moreover, even given an efficient BDE, a space-efficient encoding of the operations is still required to produce small update packages.
The need therefore is for a system that optimizes the size and number of operations to find the most effective and minimized update package size for any given original image and new image.